package com.gxc.recursion;

import java.util.*;

/**
 * N 皇后

 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *0
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位
 */
public class SolveNQueens {


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> ans = new ArrayList<>();

        int[] mid = new int[n];
        int[] left = new int[n];
        int[] right = new int[n];
        hanlde(0, n, mid, left, right, ans, res);
        return res;
    }

    public void hanlde(int cur, int n, int[] mid, int[] left, int[] right, List<String> ans, List<List<String>> res) {
        if (cur == n) {
            res.add(new ArrayList<>(ans));
            return;
        }
        int[] leftC = new int[n], rightC = new int[n];
        for (int i = 0; i < left.length-1; i++) {
            leftC[i] = left[i+1];
        }
        for (int i = 1; i < right.length; i++) {
            rightC[i] = right[i-1];
        }

        for (int i = 0; i < n; i++) {
            if (mid[i] == 0 && leftC[i] == 0 && rightC[i] == 0) {
                mid[i] = 1;
                leftC[i] = 1;
                rightC[i] = 1;
                StringBuffer buffer = new StringBuffer();
                for (int j = 0; j < n; j++) {
                    if (i==j) buffer.append("Q");
                    else buffer.append(".");
                }
                ans.add(buffer.toString());
                hanlde(cur+1, n, mid, leftC, rightC, ans, res);
                //回滚
                ans.remove(ans.size()-1);
                mid[i] = 0;
                leftC[i] = 0;
                rightC[i] = 0;
            }
        }
    }

    public List<List<String>> solveNQueens2(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    public List<List<String>> solveNQueens3(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> solutions = new ArrayList<List<String>>();
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }

    public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                //x & (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置；
                int position = availablePositions & (-availablePositions);
                //x & (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0。
                availablePositions = availablePositions & (availablePositions - 1);
                //计算最低位1的index
                int column = Integer.bitCount(position - 1);
                queens[row] = column;
                solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                queens[row] = -1;
            }
        }
    }

}
